package day_2022_7_to_8.day48;

/**
 * @author haomin
 * @date 2022/08/30 12:01
 **/
public class Day45_4_Offer10_Ⅱ_NumWays {
    class Solution {
        public int numWays(int n) {
            if(n < 2) return 1;
            int[] dp = new int[n+1];
            dp[0] = dp[1] = 1;
            for(int i = 2; i <= n; ++i){
                dp[i] = (dp[i-1]+dp[i-2]) % 1000000007;
            }
            return dp[n];
        }
    }
}